1799C - Double Lexicographically Minimum - CodeForces Solution

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;


void solve() {
    string s; cin >> s;
    sort(s.begin(), s.end());
    vector<char> sol (s.size(), ' ');
    map<char, int> mp;
    for (int i = 0; i < s.size(); i++) {
        mp[s[i]]++;
    }
    int left = 0;
    int right = s.size()-1;
    for (auto & [k,v] : mp) {
        if (v % 2 == 0) {
            int steps = v / 2; // fill this many chars
            while (steps--) {
                sol[left] = k;
                sol[right] = k;
                left += 1;
                right -= 1;
            }
            mp[k] = 0;
        } else { // odd number, need to quit here
            if (v > 2) {
                int steps = (v-1) / 2;
                while (steps--) {
                    sol[left] = k;
                    sol[right] = k;
                    left += 1;
                    right -= 1;
                }
            }
            mp[k] = 1;
            break;
        }
    }
    // check how many are remaining
    vector<char> keys; 
    for (auto & [k,v] : mp) {
        if (v > 0) keys.push_back(k);
    }
    // break into cases by the number of remaining letters
    if (keys.size() == 0) {
        for (char c : sol)  {cout << c;}
        cout << endl;
    } 
    else if (keys.size() == 1){
        string r;
        int times = mp[keys[0]];
        while (times--) {
            r += keys[0];
        }
        // print result
        for (int i = 0; i < left; i++) {
            cout << sol[i];
        }
        cout << r;
        for (int i = right + 1; i < s.size(); i++){
            cout << sol[i];
        }
        cout << endl;
    } 
    else if (keys.size() == 2) { 
        // abbb case
        string r;
        int times = mp[keys[1]] + 1;
        while (times--) {
            r += keys[1];
        }
        r[(r.size())/2] = keys[0];
        // print result
        for (int i = 0; i < left; i++) {
            cout << sol[i];
        }
        cout << r;
        for (int i = right + 1; i < s.size(); i++){
            cout << sol[i];
        }
        cout << endl;
    } 
    else {
        // multiple 
        string r; 
        for (int i = 1; i < keys.size(); i++) {
            int reps = mp[keys[i]];
            while (reps--) {
                r += keys[i];
            }
        }
        r += keys[0];
        // print result
        for (int i = 0; i < left; i++) {
            cout << sol[i];
        }
        cout << r;
        for (int i = right + 1; i < s.size(); i++){
            cout << sol[i];
        }
        cout << endl;
    }








}



int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}